package gqqnbig;

public class StringHelper
{

	/**
	 * 得到编辑距离
	 * 
	 * @return 编辑距离
	 */
	public static int getStringDistance(String strX, String strY)
	{
		char[] charArrayX = strX.toCharArray();
		char[] charArrayY = strY.toCharArray();
		return editDistance(charArrayX, charArrayX.length - 1, charArrayY, charArrayY.length - 1);
	}

	/**
	 * 动态规划解决编辑距离
	 * 
	 * editDistance(i,j)表示字符串X中[0.... i]的子串 Xi 到字符串Y中[0....j]的子串Y1的编辑距离。
	 * 
	 * @param charArrayX
	 * 
	 * @param i
	 *            字符串X第i个字符
	 * @param charArrayY
	 * @param j
	 *            字符串Y第j个字符
	 * @return 字符串X(0...i)与字符串Y(0...j)的编辑距离
	 */
	private static int editDistance(char[] charArrayX, int i, char[] charArrayY, int j)
	{
		if (i == 0 && j == 0)
		{
			// System.out.println("edit["+i+","+j+"]="+isModify(i,j));

			return charArrayX[i] == charArrayY[j] ? 0 : 1;
		}
		else if (i == 0 || j == 0)
		{
			if (j > 0)
			{
				// System.out.println("edit["+i+","+j+"]=edit["+i+","+(j-1)+"]+1");
				if (charArrayX[i] == charArrayY[j])
					return j;
				return editDistance(charArrayX, i, charArrayY, j - 1) + 1;
			}
			else
			{
				// System.out.println("edit["+i+","+j+"]=edit["+(i-1)+","+j+"]+1");
				if (charArrayX[i] == charArrayY[j])
					return i;
				return editDistance(charArrayX, i - 1, charArrayY, j) + 1;
			}
		}
		else
		{
			// System.out.println("edit["+i+","+j+"]=min( edit["+(i-1)+","+j+"]+1,edit["+i+","+(j-1)+"]+1,edit["+(i-1)+","+(j-1)+"]+isModify("+i+","+j+")");
			int ccc = minDistance(editDistance(charArrayX, i - 1, charArrayY, j) + 1, editDistance(charArrayX, i, charArrayY, j - 1) + 1,
					editDistance(charArrayX, i - 1, charArrayY, j - 1) + (charArrayX[i] == charArrayY[j] ? 0 : 1));
			return ccc;
		}

	}

	/**
	 * 求最小值
	 * 
	 * @param disa
	 *            编辑距离a
	 * @param disb
	 *            编辑距离b
	 * @param disc
	 *            编辑距离c
	 */
	private static int minDistance(int disa, int disb, int disc)
	{
		int dismin = Integer.MAX_VALUE;
		if (dismin > disa)
			dismin = disa;
		if (dismin > disb)
			dismin = disb;
		if (dismin > disc)
			dismin = disc;
		return dismin;
	}

	/**
	 * 将text重复n次，每次用seperator分离。
	 * 
	 * @param text
	 * @param seperator
	 * @param n
	 * @return
	 */
	public static String repeat(String text, String seperator, int n)
	{
		StringBuilder sb = new StringBuilder(text.length() * n);
		for (int i = 0; i < n; i++)
		{
			sb.append(text);
			sb.append(seperator);
		}

		sb.delete(sb.length() - seperator.length(), sb.length());

		return sb.toString();

	}
}
